#ifndef _TREE_H_
#define _TREE_H_

/******************************************
write by zhangliang <liangzhws@foxmail.com>
*******************************************/

#ifndef NULL

#define NULL     0

#endif

#ifndef __BOOL
#define __BOOL

typedef int bool;

#define false    0
#define true     1

#endif


#ifndef _INIT_HEAD
#define _INIT_HEAD

#define init_head(type, head) init_head_##type(head)

#endif


#ifndef __ENTRY
#define __ENTRY

#define entry(ptr, type, member) (type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))

#endif

/*******************************************
tree model:
		------
head      __>  | head | <-------   
         /      ------ <        \
        /         \     \        ---------
       /           \     \                \
      /             >  ------- <-------    \
     /             /  |  head | root   \----\-----\ 
    |             /    -------               \     |
    |            /    | father|-->head        |    |
    |           |      -------                |    |
    |           |  ---| f_son |               |    |
    |           | /    -------                |    |
    |           |/    | b_left|-->NULL        |    |
    |           /      -------                |    |
    |          /|     | b_rigt|-->NULL        |    |
    |         / |      -------                |    |
    |        /  |                             |    |
    \       /   |                             |    |
     \     <    |                             |    |
      \-------  |                     -------/    /
      |  head | |                    |  head |   /
       -------  |                     -------   /
      | father|/                     | father|--
       -------                        -------
...<--| f_son |                      | f_son | --> ...
       -------                        -------
last<-| b_left| <--    ...  <---     | b_left|
       -------                        -------
      |b_right| --->   ...  --->     |b_right|-->first
       -------                        -------

last: is represent for the last one in brother link, if only itself , last is link itself
first:is represetn for the first one in brother link, if only itself, first is link itself

*******************************************/

#define _TREE_S
#define _TREE_T

typedef struct tree_s {
	struct tree_s * head;
	struct tree_s * father;
	struct tree_s * first_son;
	struct tree_s * brother_left;
	struct tree_s * brother_right;
} tree_t ;

#define init_head_tree_t(entry) do {       \
	(entry)->head = (entry);            \
	(entry)->father = (entry);          \
	(entry)->first_son = NULL;         \
	(entry)->brother_left = (entry);    \
	(entry)->brother_right = (entry);   \
	} while(0)

/**
  @name: tree_is_empty
  @function: judge tree is empty or not
  @param: #const tree_t * head# tree head who is tree units manager
  @return: #bool# ture is empty and false is not
  @algorithm complexity: O(1)
*/
bool tree_is_empty(const tree_t * head);

/**
  @name: tree_is_exist
  @function: judge the unit in tree or not
  @param: #const tree_t * head# tree head who is tree units manager
  @param: #const tree_t * unit# tree unit that is tree node
  @return: #bool# true is exist and false isn't exist
  @algorithm complexity: O(1)
*/
bool tree_is_exist(const tree_t * head, const tree_t * unit);

/**
  @name: tree_empty
  @function: empty the tree head
  @param: tree head who is tree units manager
  @return: #void#
  @algorithm complexity: O(1) 
*/
void tree_empty(tree_t * head);

/**
  @name: tree_is_head
  @function: judge the entry is tree head or not
  @param: #tree_t * entry# one tree unit
  @return: #bool# true is tree-head and false isn't tree-head
  @algorithm complexity:O(1)
*/
bool tree_is_head(tree_t * entry);

/**
  @name: tree_is_root
  @function: judge the entry is tree root or not
  @param: #tree_t * entry# one tree unit
  @return: #bool# true is tree-root and false isn't tree-root
  @algorithm complexity: O(1)
*/
bool tree_is_root(tree_t * entry); 

/**
  @name: tree_add_son
  @function: add tree node to one tree node as it's son 
  @param: #tree_t * entry# as father node
  @param: #tree_t * unit# as son node
  @return: #void#
  @algorithm complexity: O(1)
*/
void tree_add_son(tree_t * entry, tree_t * unit);

/**
  @name: tree_del_son
  @function: del tree node from the tree node belong to tree, if the tree node not belong to any tree ,invoke error,and the tree node's children become its father's children
  @param: #tree_t * unit# tree unit
  @return: #void#
  @algorithm complexity: 
*/
void tree_del_son(tree_t * unit);

/**
  @name: tree_del_son_all
  @function: del tree node from the tree node belong to tree, if the tree node not belong to any tree ,invoke error,and the tree node's children be deleted too
  @param: #tree_t * unit# tree unit
  @return: #void#
  @algorithm complexity: O(1)
*/
void tree_del_son_all(tree_t * unit);

/**
  @name: tree_get_son
  @function: get the son of the entry node
  @param: #tree_t * entry# tree unit
  @param: #unsigned long index# index, begin from 0,
  @return: #tree_t *# tree unit, son of he entry, null is represent for entry.son[index] not exist
  @algorithm complexity: O(index)
*/
tree_t * tree_get_son(tree_t * entry,unsigned long index);

/**
  @name: tree_get_father
  @function: get the father node of the tree unit
  @param: #tree_t * unit# tree unit
  @return: #tree_t *# tree unit pointer point to tree node who is unit's father node
  @algorithm complexity: O(1)
*/
tree_t * tree_get_father(tree_t * unit);

/**
  @name: tree_get_head
  @function: get the head who is tree units manager
  @param: #tree_t * unit# tree unit
  @return: #tree_t * head# tree-head who is tree units manager
  @algorithm complexity: O(1)
*/
tree_t * tree_get_head(tree_t * unit);

/**
  @name: tree_get_root
  @function: get the tree root
  @param: #tree_t * unit# tree unit
  @return: #tree_t *# tree root
  @algorithm complexity: O(1)
*/
tree_t * tree_get_root(tree_t * unit);


#endif /* _TREE_H_ */



